#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode * traversal(vector<int> &nums, int left, int right){
        if (left >= right) return nullptr;

        int maxValueIndex = left;
        for (int i=left+1; i<right; i++){
            if(nums[i] > nums[maxValueIndex]){
                maxValueIndex = i;
            }
        }

        TreeNode * root = new TreeNode(nums[maxValueIndex]);
        root->left = traversal(nums, left, maxValueIndex);
        root->right = traversal(nums, maxValueIndex + 1, right);
        return root;
    }

    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        // TreeNode * node = new TreeNode(nums[0]);
        // if(nums.size() == 1) return node;

        // int maxValueIndex = 0;
        // for(int i=0; i<nums.size(); i++){
        //     if (nums[i] > nums[maxValueIndex]) maxValueIndex = i;
        // }

        // node->val = nums[maxValueIndex];
        // if (maxValueIndex > 0){
        //     vector<int> newVec(nums.begin(), nums.begin() + maxValueIndex);
        //     node->left = constructMaximumBinaryTree(newVec);
        // }
        // if (maxValueIndex < nums.size() - 1){
        //     vector<int> newVec(nums.begin() + maxValueIndex + 1, nums.end());
        //     node->right = constructMaximumBinaryTree(newVec);
        // }
        // return node;

        return traversal(nums, 0, nums.size());
    }
};